#include <vector>
#include <algorithm>
#include <iostream>
#include "conio.h"

using namespace std;

enum Printing_order
{
	INORDER,
	PREORDER,
	POSTORDER
};

class BST
{
private:
	struct BST_node
	{
		BST_node() : left(nullptr), right(nullptr), parent(nullptr) {}
		BST_node *left, *right, *parent;
		int key;
	};

public:
	BST (const vector<int> &preorder_array)
	{
		root = nullptr;
		for (int i_elem = 0; i_elem < preorder_array.size(); ++i_elem)
		{
			insert(preorder_array[i_elem]);
		}
	}

	void insert(int x)
	{
		if (root == nullptr)
		{
			root = new BST_node;
			root->key = x;
		}
		else
			insert_rec(x, root, nullptr);
	}

	void print(Printing_order order)
	{
		cout << endl;
		switch (order)
		{
		case Printing_order::INORDER:
				print_inorder(root);
				break;
		case Printing_order::PREORDER:
				print_preorder(root);
				break;
		case Printing_order::POSTORDER:
				print_postorder(root);
				break;
		}
		cout << endl;
	}

private:
	BST_node *root;

	void insert_rec(int x, BST_node *cur_node, BST_node *prev_node)
	{
		// if we are at the leaf - insert
		if (cur_node == nullptr)
		{
			BST_node *node = new BST_node;
			node->parent = prev_node;
			node->key = x;

			if (prev_node != nullptr)
			{
				if (x < prev_node->key)
					prev_node->left = node;
				else
					prev_node->right = node;
			}
		}
		else
		{
			if (x < cur_node->key)
				insert_rec(x, cur_node->left, cur_node);
			else
				insert_rec(x, cur_node->right, cur_node);
		}
	}

	void print_node(const BST_node *node)
	{
		cout << node->key << " ";
	}

	void print_preorder(const BST_node *node)
	{
		if (node == nullptr)
			return;

		print_node(node);
		print_preorder(node->left);
		print_preorder(node->right);
	}

	void print_inorder(const BST_node *node)
	{
		if (node == nullptr)
			return;

		print_inorder(node->left);
		print_node(node);
		print_inorder(node->right);
	}

	void print_postorder(const BST_node *node)
	{
		if (node == nullptr)
			return;

		print_postorder(node->left);
		print_postorder(node->right);
		print_node(node);
	}
};

// preorder array corresponds to the order of insertion of the elements
void main()
{
	int num_nodes;
	cout << "input the number of nodes in the tree:" << endl;
	cin >> num_nodes;

	cout << "input elements:" << endl;
	vector<int> preorder_array(num_nodes);
	for (int i_node = 0; i_node < num_nodes; ++i_node)
		cin >> preorder_array[i_node];

	BST bst(preorder_array);
	cout << "BST in preorder form :" << endl;
	bst.print(Printing_order::PREORDER);

	cout << "BST in inorder form :" << endl;
	bst.print(Printing_order::INORDER);

	cout << "BST in postorder form :" << endl;
	bst.print(Printing_order::POSTORDER);

	_getch();
}